package org.gzc.algorithm;

/**
 * @Description: 汉诺塔问题（分治算法）
 * @Author: guozongchao
 * @Date: 2020/8/19 17:35
 */
public class HanoiTower {
    private static int count=0 ; //统计步骤数
    public static void main(String[] args)  {
        hanoiTowerSolution(5,'A','B','C');
    }

    /**
     * 汉诺塔解决方案
     * @param n  盘的数量
     * @param a  盘的起始位置
     * @param b  过度位置
     * @param c  盘的目的位置
     */
    public static void hanoiTowerSolution(int n, char a, char b, char c) {
        if (n == 1) {
            System.out.printf("第%d步：从%c ---> %c\n", ++count, a, c);
        }else{
            //分 : 将当时n个盘子，先将前n-1个移动到 过度位置b（此时b作为下一次递归的目的位置，c作为过度位置）
            hanoiTowerSolution(n-1,a,c,b);
            //再将最后一个盘子直接移动到 目的位置
            System.out.printf("第%d步：从%c ---> %c\n", ++count, a, c);
            //治 : 最后将n-1个盘子从 起始位置（b作为此时起始位置） 移动到 目的位置
            hanoiTowerSolution(n-1,b,a,c);
        }
    }
}
